HiPerDOT is a specialized subset of the DOT language. DOT is covered by the Common Public License (CPL) \cite{commonpubliclicense} and is defined on the Graphviz website \cite{graphviz}.

\section{Grammar}

The following is an abstract grammar defining the HiPerDOT language. Terminals are shown in bold font and nonterminals in italics. Literal characters are given in single quotes. Parentheses ( and ) indicate grouping when needed. Square brackets [ and ] enclose optional items. Vertical bars \big| separate alternatives.

\setlength\parindent{0in}
\setlength\parskip{0.25in}

\ssp

\texttt{
{\it graph} : {\bf digraph}) [ {\it ID} ] {\bf `\{'} {\it stmt\_list} {\bf `\}'} \newline
{\it stmt\_list} : [ {\it stmt} [ {\bf `;'} ] [ {\it stmt\_list} ] ] \newline
{\it stmt} : {\it node\_stmt} \newline
          \big| {\it edge\_stmt} \newline
          \big| {\it attr\_stmt} \newline
          \big| {\it ID} {\bf `='} {\it ID} \newline
 {\it attr\_stmt} : ({\bf graph} \big| {\bf node} \big| {\bf edge}) {\it attr\_list} \newline
 {\it attr\_list} : {\bf `['} [ {\it a\_list} ] {\bf `]'} [ {\it attr\_list} ] \newline
    {\it a\_list} : {\it ID} [ {\bf `='} {\it ID} ] [ {\bf `,'} ] [ {\it a\_list} ] \newline
 {\it edge\_stmt} : ({\it node\_id} \big| {\it subgraph}) {\it edgeRHS} [ {\it attr\_list} ] \newline
   {\it edgeRHS} : {\it edgeop} ({\it node\_id} \big| {\it subgraph}) [ {\it edgeRHS} ] \newline
 {\it node\_stmt} : {\it node\_id} [ {\it attr\_list} ] \newline
   {\it node\_id} : {\it ID} \newline
  {\it subgraph} : [ {\bf subgraph} [ {\it ID} ] ] {\bf `\{'} {\it stmt\_list} {\bf `\}' } \newline
}


\dsp

\setlength\parindent{18pt}
\setlength\parskip{0in}

The keywords {\bf node}, {\bf edge}, and {\bf digraph} are case-independent.

An {\it ID} is any string of alphanumeric([a-zA-Z0-9]) characters or underscores (`\_'), not beginning with a digit.

An {\it edgeop} is -\textgreater in directed graphs and - - in undirected graphs.

An {\it a\_list} clause of the form {\it ID} is equivalent to {\it ID}={\tt true}.

The language supports C++-style comments: /* */ and //. In addition, a line beginning with a '\#' character is considered a line output from a C preprocessor (e.g., \# 34 to indicate line 34) and discarded.

Semicolons aid readability but are not required. Also, any amount of whitespace may be inserted between terminals.

As another aid for readability, HiPerDOT allows single logical lines to span multiple physical lines using the standard C covention of a backslash immediately preceeding a newline character. In addition, double-quoted strings can be concatenated using a '+' operator. As HTML strings can contain newline characters, they do not support the concatenation operator.

\section{Semantic Notes}

If a default attribute is defined using a {\bf node}, {\bf edge}, or {\bf graph} statement, or by an attribute assignment no attached to a node or edge, any object of the appropriate type defined afterwards will inherit this attribute value. This holds until the default attribute is set tot a new value, from which point the new value is used. Objects defined before a default attribute is set will have an empty string value attached to the attribute once the default attribute definition is made.s

If an edge belongs to a cluster, its endpoints belong to that cluster. Thus, where you put an edge can effect a layout, as clusters are sometimes laid out recursively.

\section{Character encodings}

The SpocDOT language assumes the alphanumeric character set. DOT is more flexible in this regard, and SpocDOT may be expanded in the future to accomodate more character sets.
